/**
 * 
 */
package dp.passed;

/**
 * @author xyyi
 * 
 */
public class JumpGame {

    /**
     * Given an array of non-negative integers, you are initially positioned at
     * the first index of the array.
     * 
     * Each element in the array represents your maximum jump length at that
     * position.
     * 
     * Determine if you are able to reach the last index.
     * 
     * For example: A = [2,3,1,1,4], return true.
     * 
     * A = [3,2,1,0,4], return false.
     */
    public boolean canJump(int[] A) {
	int maxCover = 0;
	for (int start = 0; start <= maxCover && start < A.length; start++) {
	    maxCover = Math.max(maxCover, A[start] + start);
	    if (maxCover >= A.length - 1)
		return true;
	}
	return false;
    }

    boolean canJumpA(int A[]) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function
	int[] jump = new int[A.length];
	jump[0] = 0;
	for (int i = 1; i < A.length; i++) {
	    jump[i] = Math.max(jump[i - 1], A[i - 1]) - 1;
	    if (jump[i] < 0)
		return false;
	}
	return jump[A.length - 1] >= 0;
    }

    /**
     * Jump Game II
     * 
     * Given an array of non-negative integers, you are initially positioned at
     * the first index of the array.
     * 
     * Each element in the array represents your maximum jump length at that
     * position.
     * 
     * Your goal is to reach the last index in the minimum number of jumps.
     * 
     * For example: Given array A = [2,3,1,1,4]
     * 
     * The minimum number of jumps to reach the last index is 2. (Jump 1 step
     * from index 0 to 1, then 3 steps to the last index.)
     */
    public int jump(int[] A) {
	// Start typing your Java solution below
	// DO NOT write main() function
	if (A.length <= 1)
	    return 0;

	int start = 0;
	int end = 0;
	int counter = 0;
	while (end < A.length) {
	    int max = 0;
	    counter++;
	    for (int i = start; i <= end; i++) {
		int currJump = A[i] + i;
		if (currJump >= A.length - 1) {
		    return counter;
		}
		max = Math.max(max, currJump);
	    }
	    start = end + 1;
	    end = max;
	}

	return counter;
    }

    public JumpGame() {
	// TODO Auto-generated constructor stub
    }

    int jumpDP(int A[]) {
	int steps = 0, n = A.length, f[] = new int[1000];
	if (n == 1)
	    return 0;
	for (int i = 0; i < n; i++) {
	    if (f[steps] < i)
		steps++;
	    f[steps + 1] = Math.max(f[steps + 1], i + A[i]);
	    if (f[steps + 1] >= n - 1)
		return steps + 1;
	}
	return steps;
    }

    int jumpDP1(int A[]) {
	if (A.length <= 1)
	    return 0;

	int steps = 0, currMaxCover = 0, nextMaxCover = 0;
	for (int i = 0; i < A.length; i++) {
	    if (currMaxCover < i) {
		steps++;
		currMaxCover = nextMaxCover;
		nextMaxCover = 0;
	    }
	    nextMaxCover = Math.max(nextMaxCover, i + A[i]);
	    if (nextMaxCover >= A.length - 1)
		return steps + 1;
	}

	return steps;
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
	JumpGame jg = new JumpGame();
	int[] A = { 0, 0, 2 };
	System.out.println(jg.canJump(A));

    }

}
